// =====================================================================================
//
//       Filename:  heap.h
//
//    Description:  Description d'une structure de tas, où l'élément minimal occupe la
//					racine
//
//        Version:  1.0
//        Created:  18/08/2009 09:27:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#ifndef HEAP_H_INC
#define HEAP_H_INC

#include	<iostream>

using namespace std;

template <class T,typename Compare> class HeapNode;

/**
 * \brief Classe définissant un tas sous la forme d'un arbre binaire équilibré où chaque noeud est inférieur à ses enfants
 *
 * La classe définit un tas représenté par un arbre binaire équilibré. Elle encapsule une classe de type HeapNode et permet de s'assurer de la pertinence des requêtes sur cette classe.
 * \tparam T Type des objets contenus dans l'arbre
 * \tparam Compare Classe de comparateur, dont l'opérateur () est défini, prend en arguments deux valeurs de type T, respectivement a et b, et renvoie vrai si et seulement si a<b
 */
template<class T,typename Compare=less<T> >
class Heap {
	public:
		/**
		 * \brief Constructeur standard
		 *
		 * Le constructeur ne fait que positionner la valeur de _exchange_method en comparant la taille de la structure T à la taille des pointeurs utiles à la gestion du tas
		 */
		Heap();

		/**
		 * \brief Destructeur standard
		 *
		 * Le destructeur libère les ressources mémoire allouées à l'arbre. Il détruit récursivement l'arbre et tous ses noeuds.
		 */
		~Heap() {delete root;}

		/**
		 * \brief Insère un élément dans l'arbre
		 *
		 * La fonction insère l'élément passé en argument dans l'arbre en préservant la structure ordonnée et équilibrée.
		 * \param element Nouvel élément à insérer dans l'arbre, qui est copié à la position appropriée
		 */
		void insert(const T &element);

		/**
		 * \brief Retourne le nombre d'éléments du tas
		 *
		 * \return Nombre d'éléments du tas
		 */
		unsigned int size() {return _size;}

		/**
		 * \brief Indique si le tas est vide
		 *
		 * La fonction examine la taille du tas (variable _size) et indique si celui-ci est vide.
		 * \return Vrai si le tas est vide, faux sinon
		 */
		bool empty() {return _size==0;}

		/**
		 * \brief Retourne l'élément minimal du tas
		 *
		 * L'élément minimal du tas est situé à la racine. La fonction retourne une référence vers cet élément, sans modifier le tas. Elle s'effectue avec une complexité O(1). Si le tas ne contient pas d'élément, la fonction soulève une exception.
		 * \return Référence vers l'élément minimal du tas
		 */
		T &peek() const;

		/**
		 * \brief Recherche l'élément minimal du tas et le supprime de la structure
		 *
		 * La fonction recherche l'élément minimal du tas situé à sa racine, le supprime en conservant la structure de tas et retourne une référence vers cet élément. Elle s'effectue avec une complexité O(log n). Si le tas est vide, elle soulève une exception.
		 * \return Référence vers l'élément minimal du tas
		 */
		T pop();

		/**
		 * \brief Repositionne un élément dans le tas après une modification de celui-ci
		 *
		 * La fonction doit être appelée lorsqu'un élément du tas subit une modification susceptible d'altérer la contrainte du tas. Elle repositionne l'élément afin de conserver la structure de tas.
		 * \param node Noeud dont la valeur a été modifiée
		 */
		void adjust(HeapNode<T,Compare> *node);

		/**
		 * \brief Modifie la valeur d'un élément en conservant la structure du tas
		 *
		 * La fonction modifie la valeur de l'élément spécifié tout en conservant la structure du tas. Elle peut donc nécessiter de réaliser des échanges d'éléments et sa complexité est en O(log n).
		 * \param node Noeud dont il faut modifier la valeur
		 * \param newdata Nouvelle valeur à attribuer au noeud
		 */
		void set_data(HeapNode<T,Compare> *node,const T &newdata);

		/**
		 * \brief Recherche un noeud dans l'arbre à partir de sa valeur
		 *
		 * La fonction parcourt le tas à la recherche d'un noeud dont la valeur est donnée par le paramètre pdata.
		 * L'opérateur == doit être défini pour les valeurs de type T. La complexité de l'algorithme est de O(n).
		 * \param pdata Valeur à trouver dans l'arbre
		 * \return Noeud contenant la valeur recherchée si celle-ci est trouvée, 0 sinon
		 */
		HeapNode<T,Compare> *find(const T &pdata) {return (root)?root->find(pdata):0;}

		/**
		 * \brief Affiche le tas sur le flux de sortie
		 *
		 * La fonction affiche le tas complet sur le flux de sortie spécifié en argument
		 * \param out Flux de sortie sur lequel envoyer le tas
		 */
		void display(ostream &out);
	protected:
		HeapNode<T,Compare> *root;	//!< Racine de l'arbre binaire. Le pointeur est nul si l'arbre ne contient aucun élément.
	private:
		unsigned int _size;	//!< Nombre d'éléments dans le tas. Ce nombre est utilisé dans toutes les opérations de maintenance du tas afin de garantir l'équilibre de la structure.
		Compare _compare;	//!< Instance du comparateur d'objets de type T
		bool _exchange_method;	//!< Si la valeur est vraie, seuls les contenus sont échangés lorsque l'interversion d'un noeud avec son enfant est demandée. Sinon, seuls les liens sont échangés. Lors de la construction de la classe, cette structure compare la taille des données à échanger et la valeur est positionnée de façon à minimiser la durée de l'échange

		/**
		 * \brief Retourne un pointeur vers le noeud de numéro n du tas
		 *
		 * La fonction recherche le noeud de numéro n du tas, en considérant que celui-ci est parfaitement équilibré. Le noeud de numéro 1 est la racine, et les descendants sont parcourus récursivement dans le sens gauche-droite. La fonction s'effectue en un temps de l'ordre de O(log n).
		 * \param num Numéro du noeud auquel accéder
		 * \return Pointeur vers le noeud de numéro n du tas
		 */
		HeapNode<T,Compare> *seek(unsigned int num) const;

		/**
		 * \brief Echange le noeud source avec son enfant numéro i
		 *
		 * La fonction échange le noeud spécifié par l'argument source avec son enfant numéro i. Elle garantit la bonne efficacité de la manipulation en choisissant, selon la taille du contenu T du tas, soit d'échanger directement les contenus, soit d'échanger les liens.
		 * Dans tous les cas, après l'exécution de la fonction, source contient une référence vers le noeud parent final.
		 * \param source Noeud à échanger avec son enfant
		 * \param child Numéro de l'enfant avec lequel le noeud doit être échangé
		 */
		void exchange_with_child(HeapNode<T,Compare> *&source,unsigned short child);

		/**
		 * \brief Percole le noeud vers le bas jusqu'à ce que la contrainte de tas soit respectée
		 *
		 * La fonction échange successivement le noeud avec le plus petit de ses fils jusqu'à ce que la contrainte de tas soit bien respectée, c'est-à-dire lorsque le noeud est inférieur à ses deux enfants
		 * \param node Noeud à percoler
		 */
		void move_down(HeapNode<T,Compare> *node);

		/**
		 * \brief Percole le noeud vers le haut jusqu'à ce que la contrainte de tas soit respectée
		 *
		 * La fonction échange successivement le noeud son parent jusqu'à ce que la contrainte de tas soit bien respectée, c'est-à-dire lorsque le noeud est inférieur à ses deux enfants
		 * \param node Noeud à percoler
		 */
		void move_up(HeapNode<T,Compare> *node);
};

/**
 * \brief Structure de noeud d'un tas représenté par un arbre binaire équilibré, où chaque noeud est inférieur à ses deux fils
 *
 * La classe définit une structure de noeud d'un tas représenté par un arbre binaire équilibré. Elle permet la recherche de l'élément minimal en temps constant, l'insertion et la suppression d'un élément en temps logarithmique, la recherche d'un élément en temps linéaire
 * \tparam T Type des objets contenus dans l'arbre
 * \tparam Compare Classe de comparateur, dont l'opérateur () est défini, prend en arguments deux valeurs de type T, respectivement a et b, et renvoie vrai si et seulement si a<b
 */
template<class T,typename Compare>
class HeapNode {
	friend class Heap<T,Compare>;
	public:
		/**
		 * \brief Constructeur standard
		 * \param pdata Elément à stocker dans le noeud
		 * \param pleft Fils gauche du noeud à créer
		 * \param pright Fils droit du noeud à créer
		 * \param pparent Parent du noeud à créer
		 * \param pdepth Profondeur de l'arbre, égale à 0 si l'arbre est réduit à une feuille. La valeur -1 signifie que la profondeur n'a pas été initialisée et qu'elle doit être calculée au prochain appel.
		 */
		HeapNode(const T &pdata,HeapNode *pleft,HeapNode *pright,HeapNode *pparent,int pdepth=-1):data(pdata),parent(pparent),_depth(pdepth) {children[0]=pleft;children[1]=pright;}

		/**
		 * \brief Destructeur standard
		 *
		 * Le destructeur libère les ressources associées au noeud, et notamment la mémoire allouée par les fils droit et gauche.
		 */
		~HeapNode();

		/**
		 * \brief Retourne la profondeur de l'arbre
		 *
		 * La fonction retourne la profondeur de l'arbre. Si celle-ci a déjà été calculée et stockée dans la variable depth, elle est retournée directement. Sinon, elle est calculée à partir de celle des enfants.
		 */
		int depth();
	protected:
		T data;	//!< Valeur contenue dans le noeud courant
		HeapNode<T,Compare> *children[2];	//!< Fils du noeud courant
		HeapNode<T,Compare> *parent;	//!< Parent du noeud courant, 0 si le noeud est à la racine de l'arbre

		/**
		 * \brief Recherche un élément dans l'arbre
		 *
		 * La fonction recherche l'élément passé en argument et retourne dans l'argument element un pointeur vers la feuille qui le contient. Si l'élément n'est pas trouvé, la fonction retourne faux et element contient la feuille de l'arbre où s'est terminée la recherche. Sa complexité est de O(n).
		 * \param source Elément à rechercher dans l'arbre
		 * \return Pointeur vers l'élément recherché s'il est trouvé, 0 sinon
		 */
		HeapNode<T,Compare> *find(const T &source);

		/**
		 * \brief Affiche le tas issu du noeud courant sur un flux de sortie
		 *
		 * La fonction affiche le tas issu du noeud courant sur un flux de sortie en le préfixant par un alinéa, puis elle affiche les sous-tas issus des deux enfants.
		 * \param out Flux de sortie utilisé pour l'affichage
		 * \param border Taille de l'alinéa à insérer
		 */
		void display(ostream &out,int border);
	private:
		int _depth;	//!< Profondeur du sous-arbre issu du noeud courant. La profondeur est nulle si le sous-arbre est une feuille. Sinon elle est égale à la profondeur maximale des deux sous-arbres issus des fils gauche et droit augmentée de un.
		Compare _compare;	//!< Instance du comparateur d'objets de type T
};

#include	"heap.cpp"

#endif /* HEAP_H_ */
